package leetcode;

/**
 * Created by Ghost on 2014/11/5 0005.
 */
public class Unique_Paths {
    public int uniquePaths2(int m, int n) {
        int N = m+n-2;
        double res = 1;
        int k = m-1;
        for (int i = 1; i <= k; i++)
            res = res * (N - k + i) / i;
        return (int)res;
    }
    public int uniquePaths(int m, int n) {
        int[][] w = new int[m][n];
        for(int i=0;i<n;i++)
            w[0][i] = 1;
        for(int i=0;i<m;i++){
            w[i][0] = 1;
        }

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                w[i][j]= w[i-1][j]+w[i][j-1];
            }
        }
        return w[m-1][n-1];
    }
    public static void main(String[] args){
        System.out.println(new Unique_Paths().uniquePaths(1,2));
    }
}
